from calendar import c
from cmath import inf
from math import ceil, gcd, sqrt, log2
import os
import sys
from io import BytesIO, IOBase
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop
mod = 10 ** 9 + 7
mod1 = 998244353
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
def lcm(a, b):
return a*b//gcd(a, b)
val = lambda n, a, i: i*(n-i) if i == 0 or a[i] != a[i-1] else 0
n, m = map(int, input().split())
a = list(map(int, input().split()))
cur = n * (n + 1) // 2
for i in range(n):
cur += val(n, a, i)
for _ in range(m):
i, x = map(int, input().split())
i -= 1
cur -= val(n, a, i)
if i + 1 < n:
cur -= val(n, a, i + 1)
a[i] = x
cur += val(n, a, i)
if i + 1 < n:
cur += val(n, a, i + 1)
print(cur)#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N = 1e5 + 5;
int a[N];
void solve() {
int n, m;
cin >> n >> m;
ll ans = 1ll * n * (n + 1) / 2;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] != a[i - 1]) ans += 1ll * (i - 1) * (n - i + 1);
}
a[n + 1] = 0;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
if (a[x] == y) {
cout << ans << '\n';
continue;
}
if (a[x] == a[x - 1]) ans += 1ll * (x - 1) * (n - x + 1);
if (a[x] == a[x + 1]) ans += 1ll * x * (n - x);
if (a[x] != a[x - 1] && y == a[x - 1]) ans -= 1ll * (x - 1) * (n - x + 1);
if (a[x] != a[x + 1] && y == a[x + 1]) ans -= 1ll * x * (n - x);
a[x] = y;
cout << ans << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
return 0;
}402. Remove K Digits | 97. Interleaving String |
543. Diameter of Binary Tree | 124. Binary Tree Maximum Path Sum |
1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts | 501A - Contest |
160A- Twins | 752. Open the Lock |
1535A - Fair Playoff | 1538F - Interesting Function |
1920. Build Array from Permutation | 494. Target Sum |
797. All Paths From Source to Target | 1547B - Alphabetical Strings |
1550A - Find The Array | 118B - Present from Lena |
27A - Next Test | 785. Is Graph Bipartite |
90. Subsets II | 1560A - Dislike of Threes |
36. Valid Sudoku | 557. Reverse Words in a String III |
566. Reshape the Matrix | 167. Two Sum II - Input array is sorted |
387. First Unique Character in a String | 383. Ransom Note |
242. Valid Anagram | 141. Linked List Cycle |
21. Merge Two Sorted Lists | 203. Remove Linked List Elements |